<!DOCTYPE html>
<html lang="en">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Alias Analysis</title>
<link rel="stylesheet" type="text/css" href="https://gcc.gnu.org/gcc.css" />
</head>

<body>
<h1>Alias Analysis</h1>

<p>June 29, 1998</p>

<p>We are pleased to announce that Mark Mitchell Consulting, as
part of a continuing contract with the Accelerated Strategic Computing
Initiative (ASCI) program at Los Alamos National Laboratory, has
contributed a framework to improve alias analysis in the compiler.  It
is currently used to propagate alias information provided by the
language front ends into the optimization passes of the compiler.
Typically this information is based on the type assigned to an object
by the programmer.</p>

<p>This code is an excellent complement to the "base address" alias
analysis code contributed by John Carr last year.  The compiler uses
information from both Mark and John's contributions during its
optimization passes to improve code.</p>

<p>Here's some code which shows the benefit of Mark's contribution:</p>

<pre>
  double  u_m;
  double  v_m;

  typedef struct s {
    int     n_m;
    double* x_m;
    double* a_m;
    double* b_m;
  } s;

  void f(struct s* s)
  {
    int i;
    for (i=0; i &lt; s-&gt;n_m; ++i)
      s-&gt;x_m[i] = (u_m * s-&gt;a_m[i]) + (v_m * s-&gt;b_m[i]);
  }
</pre>

<p>This is a boiled-down C version of a C++ scientific computation
program.  In the old days, the compiler would reload <code>s-&gt;n_m</code>,
<code>s-&gt;a_m</code>, <code>s-&gt;b_m</code>, and <code>s-&gt;x_m</code> inside
the loop, for fear that the store into <code>s-&gt;x_m[i]</code> might have
altered them.  Now, however, since <code>s-&gt;x_m[i]</code> is a
<code>double</code>, and <code>s-&gt;a_m</code> is a <code>double*</code>, 
those loads are hoisted out of the loop. Here is a side by side comparison
of MIPS code generated for the loop.</p>

<pre>
          OLD                                   NEW
  .L8:
          sll     $4,$5,3
          addu    $3,$4,$3
          l.d     $f1,0($3)                     l.d     $f0,0($4)
          #nop                                  #nop
          mul.d   $f1,$f3,$f1                   mul.d   $f0,$f3,$f0
          lw      $2,12($6)      # s-&gt;b_m
          #nop
          addu    $2,$4,$2
          l.d     $f0,0($2)                     l.d     $f1,0($5)
          #nop                                  #nop
          mul.d   $f0,$f2,$f0                   mul.d   $f1,$f2,$f1
          lw      $3,4($6)       # s-&gt;x_m
          add.d   $f1,$f1,$f0                   addu    $5,$5,8
          addu    $4,$4,$3                      add.d   $f0,$f0,$f1
                                                addu    $4,$4,8
          s.d     $f1,0($4)
          lw      $2,0($6)       # s-&gt;n_m
          addu    $5,$5,1                       addu    $3,$3,1
          slt     $2,$5,$2                      slt     $2,$3,$7
                                                s.d     $f0,0($6)
          .set    noreorder                     .set    noreorder
          .set    nomacro                       .set    nomacro
          bnel    $2,$0,.L8                     bne     $2,$0,.L8
          lw      $3,8($6)       # s-&gt;a_m       addu    $6,$6,8
</pre>

<p>In addition to removal of redundant loads, the scheduler has more freedom
to rearrange instructions to avoid pipeline stalls and the resulting
code is scheduled better.</p>

<p>Mark will implement the C9x <code>restrict</code> keyword using
this framework.  In addition, we plan on using the framework Mark has
built to propagate aliasing information for memory references
generated by the compiler for prologue/epilogue code, register spills,
and other memory references.</p>

<p> To enable the new alias code use the argument <b>-fstrict-aliasing</b>;
in the future this option will be enabled by default.</p>

<p>John's alias code will remain in the compiler as it provides another way to
determine what memory addresses conflict.  John's code attempts to track what
base value is used by memory references.  Depending on the base values it
may be possible to determine that two memory references can not conflict.
For example, memory references into the static store can not conflict with
stack or heap accesses.</p>

<p>John's code actually tracks values as they migrate from one register to
another or are altered in safe ways (for example, addition of a constant does
not change a base value).</p>

</body>
</html>
